#pragma once
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
#include<assert.h>
using namespace std;
#include"Iterator.h"//反向迭代器：复用
namespace cfy
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
		typedef ReverseIterator<iterator, T&, T*> reverse_iterator;

		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}
		const_iterator begin() const
		{
			return _start;
		}
		const_iterator end() const
		{
			return _finish;
		}

		reverse_iterator rbegin()//反向
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()//反向
		{
			return reverse_iterator(begin());
		}

		T& operator[](size_t pos)
		{
			assert(pos < size());
			return _start[pos];//注意
		}

		const T& operator[](size_t pos) const//重载
		{
			assert(pos < size());
			return _start[pos];
		}

		vector()//构造
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{}

		////传统写法 v2(v1)
		//vector(const vector<T>& v)
		//	:_start(nullptr)
		//	, _finish(nullptr)
		//	, _endofstorage(nullptr)
		//{
		//	//_start = new T[v.capacity()];
		//	//……
		//	reserve(v.capacity());
		//	for (const auto& e : v)//必须&， 否则会拷贝构造调用拷贝构造，因为如果每一个元素(T)也都是vector，这就会导致拷贝构造调用拷贝构造
		//	{
		//		push_back(e);
		//	}

		//}
		vector(size_t n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			reserve(n);
			for (size_t i = 0; i < n; i++)
			{
				push_back(val);
			}
		}

		vector(int n, const T& val = T())//解决vector8的注释中的问题
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			reserve(n);
			for (size_t i = 0; i < n; i++)
			{
				push_back(val);
			}
		}

		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		//现代写法
		vector(const vector<T>& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			vector<T> tmp(v.begin(), v.end());
			swap(tmp);//this和tmp进行swap
		}


		~vector()//析构
		{
			delete[] _start;
			_start = _finish = _endofstorage = nullptr;
		}

		//v1 = v2
		//v1 = v1;虽然会付出代价，但是能保证不会出错，极少数情况，能保证正确性，所以可以容忍
		vector<T>& operator=(vector<T> v)//由于直接swap，因此不能传引用
		{
			swap(v);
			return *this;
		}
		void reserve(size_t n)//注意迭代器失效问题
		{

			if (n > capacity())
			{
				size_t oldSize = size();
				T* tmp = new T[n];
				if (_start)
				{
					//memcpy(tmp, _start, sizeof(T) * size());
					for (size_t i = 0; i < size(); i++)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				_start = tmp;
				_finish = tmp + oldSize;
				_endofstorage = _start + n;
			}
		}
		void resize(size_t n, T val = T())
		{
			if (n > capacity())
			{
				reserve(n);
			}
			if (n > size())
			{
				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
			else
			{
				_finish = _start + n;
			}
		}
		bool empty() const
		{
			return _finish == _start;
		}

		size_t size() const
		{
			return _finish - _start;
		}

		size_t capacity() const
		{
			return _endofstorage - _start;
		}

		void push_back(const T& x)
		{
			if (_finish == _endofstorage)
			{
				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);
			}

			*_finish = x;
			++_finish;

		}
		void pop_back()
		{
			assert(!empty());
			--_finish;

		}

		//迭代器失效问题：野指针问题：异地扩容导致
		iterator insert(iterator pos, const T& val)//不传引用是因为有左值的影响：常量、v.begin()
		{
			assert(pos >= _start);
			assert(pos < _finish);
			if (_finish == _endofstorage)
			{
				size_t len = pos - _start; // 处理失效问题，记录相对位置
				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);

				//扩容导致pos迭代器失效，需要更新处理一下
				pos = _start + len;
			}

			//挪动数据
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				end--;
			}
			*pos = val;
			++_finish;

			return pos;

		}

		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);
			iterator begin = pos + 1;
			while (begin < _finish)
			{
				*(begin - 1) = *begin;
				++begin;
			}

			--_finish;
			return pos;
		}

		void swap(vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstorage, v._endofstorage);
		}
		void clear()
		{
			_finish = _start;//不能置空，会发现内存泄漏
		}

	private://成员变量和_size _capacity的本质是一样的，只不过表示方法不一样
		iterator _start;
		iterator _finish;
		iterator _endofstorage;
	};

	void test_vector1()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		for (size_t i = 0; i < v.size(); i++)
		{
			cout << v[i] << " ";
		}
		cout << endl;
		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
		v.pop_back();
		v.pop_back();
		v.pop_back();
		v.pop_back();


		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void test_vector2()
	{
		vector<int> v;
		v.resize(10, -1);
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
		v.resize(5);
		for (auto e : v)
		{
			cout << e << " ";
		}
	}

	void test_vector3()
	{
		vector<int> v;
		v.resize(10, -1);
		//v.reserve(10);

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
		v.insert(v.begin(), -10);
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;


	}
	void test_vector4()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		//v.push_back(4);

		vector<int>::iterator it = find(v.begin(), v.end(), 3);
		if (it != v.end())
		{
			v.insert(it, 30);
		}
		it--;
		(*it)++;
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
		cout << *it;
	}
	void test_vector5()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);

		//it失效还是不失效? 和平台有关:vs失效，Linux C++11版本不失效，
		//g++相对更宽容，因为实现方式就是我们采用的模拟实现方式。但仍然看成失效
		vector<int>::iterator it = find(v.begin(), v.end(), 3);
		if (it != v.end())
		{
			v.erase(it);
		}
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
		cout << *it;
	}
	//void test_vector6()
	//{
	//	//要求删除所有的偶数：必须考虑迭代器失效
	//	std::vector<int> v;
	//	v.push_back(1);
	//	v.push_back(2);
	//	v.push_back(3);
	//	v.push_back(4);

	//	std::vector<int>::iterator it = v.begin();
	//	while (it != v.end())
	//	{
	//		if ((*it) % 2 == 0)
	//		{
	//			it = v.erase(it);//返回值更新迭代器
	//		}
	//		else
	//		{
	//			++it;
	//		}
	//	}
	//	for (auto e : v)
	//	{
	//		cout << e << " ";
	//	}
	//	cout << endl;
	//	
	//}
	void test_vector6()
	{
		//要求删除所有的偶数：必须考虑迭代器失效
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		//v.push_back(5);

		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			if ((*it) % 2 == 0)
			{
				it = v.erase(it);//返回值更新迭代器
			}
			else
			{
				++it;
			}
		}
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

	}
	void test_vector7()
	{

		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		//v.push_back(5);

		vector<int> v1(v);

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		vector<int> v2;
		v2.push_back(10);
		v2.push_back(20);
		v1 = v2;
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

	}
	void test_vector8()
	{
		std::string str("hello");
		vector<int> v(str.begin(), str.end());
		for (auto e : v)
		{
			cout << e << ' ';
		}
		cout << endl;

		//vector<int> v1(10, 1); //就这种会出现问题,因为调用会调用到InputIterator
		////原因：上面的1最好的选择就是利用模板实例化，因此就会last接收1，造成非法的间接寻址
		////解决方案：再加上一个构造的重载函数来解决这种问题；直接改成int的话，不符合库的思想
		////而且通过源代码也可以看出这里用到了：再加上一个重载函数的方式
		////vector<char> v1(10, 'A');//肯定会选择val对应的构造函数
		//for (auto e : v1)
		//{
		//	cout << e << ' ';
		//}
		//cout << endl;

	}

	void test_vector9()
	{
		vector<vector<int>> vv;
		vector<int> v(5, 1);
		vv.push_back(v);
		vv.push_back(v);
		vv.push_back(v);
		vv.push_back(v);
		vv.push_back(v);

		for (size_t i = 0; i < vv.size(); i++)
		{
			for (size_t j = 0; j < vv[i].size(); j++)
			{
				cout << vv[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;
	}
	void test_vector10()
	{
		vector<string> v;
		v.push_back("1111111111111");
		v.push_back("1111111111111");
		v.push_back("1111111111111");
		v.push_back("1111111111111");
		v.push_back("1111111111111");
		for (size_t i = 0; i < v.size(); i++)
		{
			for (size_t j = 0; j < v[i].size(); j++)
			{
				cout << v[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;
	}
}

